package C059;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c01_02
 * Package: C059
 * Description: 邻接表实现拓扑排序
 *
 * @Author BCXJ
 * @Create 2025/10/8 22:02
 * @Version 1.0
 * @Since 1.0
 */
public class c01_02 {
    public static void main(String[] args) {
//        int[][] arr = {{1,0},{2,0},{3,1},{3,2}};
//        int[][] arr = {{0, 1}, {1, 2}, {1, 0}};
        int[][] arr = {{0, 1}};
        System.out.println(Arrays.toString(findOrder(2, arr)));
    }



    static List<List<Integer>> grap = new ArrayList<>(2000);
    static {
        for (int i = 0; i < 2000; i++) {
            grap.add(new ArrayList<>());
        }
    }
    // 入度表
    static int[] indegree = new int[2000];
    // 队列
    static int[] queue = new int[2000];
    static int l = 0, r = 0;
    public static int[] findOrder(int numCourses, int[][] prerequisites) {

        // 初始化
        init(numCourses);
        // 建图
        for (int i = 0; i < prerequisites.length; i++) {
            addEdge(prerequisites[i][1], prerequisites[i][0]);
        }

        // 入度统计
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) {
                queue[r ++] = i;
            }
        }

        // 结果计算
        int[] res = new int[numCourses];
        int count = 0;
        while(l < r) {
            // 弹出元素
            int curNode = queue[l++];
            res[count ++] = curNode;
            // 遍历邻边 ， 更新入度表, 更新队列
            for (Integer node : grap.get(curNode)) {
                indegree[node] --;
                if(indegree[node] == 0) {
                    queue[r ++] = node;
                }
            }
        }

        return count == numCourses ? res : new int[]{};
    }

    private static void addEdge(int from, int to) {
        // 加边
        grap.get(from).add(to);
        // 入度统计
        indegree[to] ++;
    }


    private static void init(int numCourses) {
        // 图置空
        for (int i = 0; i < numCourses; i++) {
            grap.get(i).clear();
        }
        // 入度表置空
        Arrays.fill(indegree, 0);
        // 队列置空
        Arrays.fill(queue, 0);
        l = r = 0;
    }
}
